﻿#include <iostream>

#define X_MAX 9
#define Y_MAX 10

/**
 * 暴力递归
 * @param x
 * @param y
 * @param targetX
 * @param targetY
 * @param remainStep 剩余多少步
 */
static int recur(int x, int y, int targetX, int targetY, int remainSteps)
{
	if (remainSteps < 0) return 0;

	if (x < 0 || x >= X_MAX || y < 0 || y >= Y_MAX) return 0;

	if (remainSteps == 0)
	{
		return (x == targetX && y == targetY) ? 1 : 0;
	}

	return recur(x - 1, y + 2, targetX, targetY, remainSteps - 1) +
		recur(x - 2, y + 1, targetX, targetY, remainSteps - 1) +
		recur(x - 2, y - 1, targetX, targetY, remainSteps - 1) +
		recur(x - 1, y - 2, targetX, targetY, remainSteps - 1) +
		recur(x + 1, y - 2, targetX, targetY, remainSteps - 1) +
		recur(x + 2, y - 1, targetX, targetY, remainSteps - 1) +
		recur(x + 2, y + 1, targetX, targetY, remainSteps - 1) +
		recur(x + 1, y + 2, targetX, targetY, remainSteps - 1);
}

static int getDp(int* dp, int x, int y, int remain, int xSize, int ySize)
{
	if (x < 0 || x >= xSize || y < 0 || y >= ySize) return 0;

	return dp[x + y * xSize + remain * ySize * xSize];
}

static int byStrictTable(int x, int y, int targetX, int targetY, int remainSteps)
{
	int xSize = X_MAX;
	int ySize = Y_MAX;
	int remainSize = remainSteps + 1;
	int* dp = (int*)malloc(xSize * ySize * remainSize * sizeof(int));
	memset(dp, 0, xSize * ySize * remainSize * sizeof(int));

	// dp[remain][y][x] = dp(x + y * xSize + remain * ySize * xSize)

	dp[targetX + targetY * xSize] = 1;
	for (int remain = 1; remain <= remainSteps; remain++)
	{
		for (int y = 0; y < ySize; y++)
		{
			for (int x = 0; x < xSize; x++)
			{
				dp[x + y * xSize + remain * xSize * ySize] =
					getDp(dp, x - 1, y + 2, remain - 1, xSize, ySize) + 
					getDp(dp, x - 2, y + 1, remain - 1, xSize, ySize) +
					getDp(dp, x - 2, y - 1, remain - 1, xSize, ySize) + 
					getDp(dp, x - 1, y - 2, remain - 1, xSize, ySize) +
					getDp(dp, x + 1, y - 2, remain - 1, xSize, ySize) +
					getDp(dp, x + 2, y - 1, remain - 1, xSize, ySize) +
					getDp(dp, x + 2, y + 1, remain - 1, xSize, ySize) +
					getDp(dp, x + 1, y + 2, remain - 1, xSize, ySize);
			}
		}
	}

	int res = dp[x + y * xSize + remainSteps * xSize * ySize];
	free(dp);
	return res;
}

/**
 * 象棋中的马停在(0,0)位置，问走到(x,y)需要走k步，有多少种方法？
 * 棋盘大小9x10
 */
int main_ChineseChess()
{
	int remainSteps = 11;
	int startX = 0;
	int startY = 0;
	int targetX = 6;
	int targetY = 7;
	int methodCount = recur(startX, startY, targetX, targetY, remainSteps);

	printf("%d, %d\n", methodCount, byStrictTable(startX, startY, targetX, targetY, remainSteps));
	return 0;
}